package cn.bellychang.wangzheng.backtracking;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author ChangLiang
 * @date 2021/2/19
 */
public class BackpackSolution {

    /**
     * 存储背包中物品总重量的最大值
     */
    public int maxW = Integer.MIN_VALUE;

    /**
     * 下标表示物品序号，值表示是否放进背包:1放，0不放
     */
    private int[] currentAnswer;

    /**
     * 存储所有解(map key表示放进去的重量，value表示对应重量的物品放法)
     * 最终所有最优解为bestAnswerMap.get(maxW)
     */
    private Map<Integer, List<int[]>> bestAnswerMap = new HashMap<>();


    /**
     *
     * 我们可以把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。
     * 先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。
     *
     * @param i 表示考察到哪个物品了
     * @param cw 表示当前已经装进去的物品的重量和
     * @param items 表示每个物品的重量
     * @param n 表示物品个数
     * @param w 背包重量
     */
    public void f(int i, int cw, int[] items, int n, int w) {

        if (currentAnswer == null) {
            currentAnswer = new int[n];
        }

        // 函数入口处的 if 分支表明递归结束条件，并保证 maxW 跟踪所有选择中的最大值
        if (cw == w || i == n) {
            // cw==w 表示装满了  i==n表示已经考察完所有的物品
            if (cw >= maxW) {
                maxW = cw;
                int[] bestAnswer = new int[currentAnswer.length];
                for (int j = 0; j < currentAnswer.length; j++) {
                    bestAnswer[j] = currentAnswer[j];
                }
                if (bestAnswerMap.containsKey(cw)) {
                    bestAnswerMap.get(cw).add(bestAnswer);
                } else {
                    List<int[]> list = new ArrayList<>();
                    list.add(bestAnswer);
                    bestAnswerMap.put(cw, list);
                }
            }
            return;
        }

        // 表示不选择当前物品，直接考虑下一个（第 i+1 个），故 cw 不更新
        currentAnswer[i] = 0;
        f(i + 1, cw, items, n, w);

        // 已经超过背包可以承受的重量，就不要再装了
        if (cw + items[i] <= w) {
            // 选择了当前物品，故考虑下一个时，cw 通过入参更新为 cw + items[i]
            currentAnswer[i] = 1;
            f(i + 1, cw + items[i], items, n, w);
        }
    }

    public List<int[]> getBestAnswer() {
        List<int[]> ints = bestAnswerMap.get(maxW);
        return ints;
    }

}
